package cn.bellychang.leetcode.question091;

/**
 * @author ChangLiang
 * @date 2021/3/18
 */
public class Solution {

    public int numDecodings(String s) {

        char[] chars = s.toCharArray();
        // 利用递归函数decode 从最后一个字符开始
        return decode(chars, chars.length - 1);
    }

    private int decode(char[] chars, int index){
        // 终止条件 第一个字符只能有一种解码方法
        if (index <= 0) {
            return 1;
        }

        int count = 0;

        // 考虑当前字符和它前面的字符
        char curr = chars[index];
        char prev = chars[index - 1];

        // curr 可取的范围是0-9 但取0的情况包含在 prev下了 所以其为 1--9
        // prev 可取的范围也是0-9
        // 但两者配合能够产生组合的 prev 1 -- curr 0--9 | prev 2 -- curr 0--6

        // 如果当前字符比0大 那么其前面的字符有m种可能 加上这个比0大的字符 仍是m种
        if (curr >= '1' && curr <= '9') {
            count = decode(chars, index - 1);
        }

        // 要不要考虑curr为0的情况呢
        // 如果其前一个字符是1或者2 这样就可以构成10 或 20

        // 之后要考虑其前一个字符了 这里我们只需要注意由curr和prev所构成的数字 一定要满足一个条件
        // 其值必须在1到26之间 否则无法对其进行解码
        if (prev == '1' || (prev == '2' && curr <= '6')) {
            // 这种情况下 其可能性为前面prev前面的K种可能 + m种
            count += decode(chars, index - 2);
        }

        return count;
    }
}
